package com.comic_algorithm;

public class MyLinkedList {
	//头节点指针
	private Node head;
	//尾节点指针
	private Node last;
	//链表实际长度
	private int size;
	
	/**
	 * 链表插入元素
	 * @param data 插入元素
	 * @param index 插入位置
	 * @throws Exception
	 */
	public void insert(int data, final int index) throws Exception {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("超出链表节点范围！");
		}
		Node insertedNode = new Node(data);
		if (0 == size) {
			//空链表
			head = insertedNode;
			last = insertedNode;
		} else if (0 == index) {
			//插入头部
			insertedNode.next = head;
			head = insertedNode;
		} else if (index == size) {
			//插入尾部
			last.next = insertedNode;
			last = insertedNode;
		} else {
			//插入中间
			Node prevNode = get(index - 1);
			insertedNode.next = prevNode.next;
			prevNode.next = insertedNode;
		}
		++size;
	}
	
	/**
	 * 链表删除元素
	 * @param index 删除的位置
	 * @return 被删除的元素
	 * @throws Exception
	 */
	public Node remove(final int index) throws Exception {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("超出链表节点范围！");
		}
		Node removedNode = null;
		if (0 == index) {
			//删除头节点
			removedNode = head;
			head = head.next;
		} else if (size - 1 == index) {
			//删除尾节点
			Node prevNode = get(index - 1);
			removedNode = prevNode.next;
			prevNode.next = null;
			last = prevNode;
		} else {
			//删除中间节点
			Node prevNode = get(index - 1);
			Node nextNode = prevNode.next.next;
			removedNode = prevNode.next;
			prevNode.next = nextNode;
		}
		--size;
		return removedNode;
	}
	
	/**
	 * 链表查找元素
	 * @param index 查找的位置
	 * @return 查找到的节点
	 * @throws Exception
	 */
	public Node get(final int index) throws Exception {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("超出链表节点范围！");
		}
		Node temp = head;
		for (int i = 0; i < index; ++i) {
			temp = temp.next;
		}
		return temp;
	}
	
	/**
	 * 输出链表
	 */
	public void output() {
		Node temp = head;
		while (null != temp) {
			System.out.println(temp.data);
			temp = temp.next;
		}
	}
	
	/**
	 * 链表节点
	 */
	private static class Node {
		int data;
		Node next;
		
		Node (int data) {
			this.data = data;
		}

	}
	
	public static void main(String[] args) throws Exception {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.insert(3, 0);
		myLinkedList.insert(7, 1);
		myLinkedList.insert(9, 2);
		myLinkedList.insert(5, 3);
		myLinkedList.insert(6, 1);
		myLinkedList.remove(0);
		myLinkedList.output();
	}
	
}
